package leetcode.editor.cn.q1_300.q200;
//请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 
//
// 实现词典类 WordDictionary ： 
//
// 
// WordDictionary() 初始化词典对象 
// void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 
// bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 
//'.' ，每个 . 都可以表示任何一个字母。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//["WordDictionary","addWord","addWord","addWord","search","search","search",
//"search"]
//[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
//输出：
//[null,null,null,null,false,true,true,true]
//
//解释：
//WordDictionary wordDictionary = new WordDictionary();
//wordDictionary.addWord("bad");
//wordDictionary.addWord("dad");
//wordDictionary.addWord("mad");
//wordDictionary.search("pad"); // 返回 False
//wordDictionary.search("bad"); // 返回 True
//wordDictionary.search(".ad"); // 返回 True
//wordDictionary.search("b.."); // 返回 True
// 
//
// 
//
// 提示： 
//
// 
// 1 <= word.length <= 25 
// addWord 中的 word 由小写英文字母组成 
// search 中的 word 由 '.' 或小写英文字母组成 
// 最多调用 10⁴ 次 addWord 和 search 
//

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

/**
 * 基本思路还是前缀树
 * 这里只是使用 通过节点的数量
 * 如果加上 结束节点的数量 会块很多
 */
public class Q211_DesignAddAndSearchWordsDataStructure {
    //leetcode submit region begin(Prohibit modification and deletion)
    class WordDictionary {

        public char me;
        // 通过的数量
        public int postNum = 0;
        // 子节点
        public WordDictionary[] children = new WordDictionary[26];

        public WordDictionary() {

        }

        public WordDictionary(char c) {
            this.me = c;
        }

        public void addWord(String word) {
            char[] chars = word.toCharArray();
            WordDictionary cur = this;
            for (char c : chars) {
                int i = c - 'a';
                if (cur.children[i] == null) {
                    cur.children[i] = new WordDictionary(c);
                }
                cur = cur.children[i];
                cur.postNum++;
            }
        }

        public boolean search(String word) {
            char[] chars = word.toCharArray();
            List<WordDictionary> outer = new ArrayList<>();
            outer.add(this);
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                List<WordDictionary> inner = new ArrayList<>();
                if (c == '.') {
                    inner.addAll(outer.stream().flatMap(o -> Arrays.stream(o.children)).filter(Objects::nonNull).collect(Collectors.toList()));
                } else {
                    inner.addAll(outer.stream().filter(Objects::nonNull).map(o -> o.children[c - 'a']).filter(Objects::nonNull).collect(Collectors.toList()));
                }
                if (inner.size() == 0) {
                    return false;
                }
                outer = new ArrayList<>(inner);
            }

            int sum = outer.stream().mapToInt(c -> c == null ? 0 : c.postNum).sum();
            int sum1 = outer.stream().mapToInt(c -> Arrays.stream(c.children).filter(Objects::nonNull).mapToInt(ch -> ch.postNum).sum()).sum();
            return sum > sum1;
        }
    }

    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */
    //leetcode submit region end(Prohibit modification and deletion)
    public static void main(String[] args) {
        WordDictionary wordDictionary = new Q211_DesignAddAndSearchWordsDataStructure().new WordDictionary();
        // TO TEST
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        System.out.println(wordDictionary.search("pad")); // 返回 False
        System.out.println(wordDictionary.search("bad")); // 返回 True
        System.out.println(wordDictionary.search(".ad")); // 返回 True
        System.out.println(wordDictionary.search("b..")); // 返回 True
        wordDictionary.addWord("apple");
        System.out.println(wordDictionary.search("app")); // 返回 false
        System.out.println(wordDictionary.search("a..")); // 返回 false
        wordDictionary.addWord("app");
        System.out.println(wordDictionary.search("app")); // 返回 true
        System.out.println(wordDictionary.search("a..")); // 返回 true

//        wordDictionary.addWord("at");
//        wordDictionary.addWord("and");
//        wordDictionary.addWord("an");
//        wordDictionary.addWord("add");
//        System.out.println(wordDictionary.search("a"));
//        System.out.println(wordDictionary.search(".at"));
//        wordDictionary.addWord("bat");
//        System.out.println(wordDictionary.search(".at"));
//        System.out.println(wordDictionary.search("an."));
//        System.out.println(wordDictionary.search("a.d."));
//        System.out.println(wordDictionary.search("b."));
//        System.out.println(wordDictionary.search("a.d"));
//        System.out.println(wordDictionary.search("."));
//        [null,null,null,null,null,false,false,null,false,true,false,false,false,false] false
//        [null,null,null,null,null,false,false,null,true,true,false,false,true,false] true
    }
}